//#define _CRT_SECURE_NO_WARNINGS  1
////一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
////一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考
//#include<string>
//#include<iostream>
//using namespace std;
//class Solution {
//public:
//	int search(vector<int>& nums, int target) {
//		int left = 0;
//		int right = nums.size() - 1;//定义target在左比右开区间，[left,right]
//		while (left <= right)//当left ==right 时依然有效所以<=
//		{
//			int middle = left + ((right - left) / 2);//防止溢出，等同与（left+right
/////2
//			if (nums[middle] > target)
//			{
//				right = middle - 1;//target在做区间，所以[left,middle-1]
//			}
//			else if (nums[middle] < target)
//			{
//				left = middle + 1;//target  在右区间,所以[middle+1,right]
//			}
//			else {
//				//nums[middle] == target
//				return middle;
//			}
//		}
//		return -1;
//
//	}
//};
//
//
//class Solutio {
//public:
//	int search(vector<int>& nums, int target) {
//		int left = 0;
//		int right = nums.size();//定义target在左闭右开的区间即[left,right)
//		while (left < right)//因为left==right的时候，在[left，right)是无效的，所以用<
//		{
//			int middle = left + ((right - left) >> 1);
//			if (nums[middle] > target)
//			{
//				right = middle;//target在左区间，在[left,middle]中
//			}
//			else if (nums[middl] < target)
//			{
//				left = middle + 1;//target 在右区间，在[middle +1,right)中
//			}
//			else {
//				//nums[middle]==target
//				return middle;
//			}
//		}
//		return -1;
//	}
//};
//
//class Solutio {
//public:
//	int search(vector<int>& nums, int target)
//	{
//		int left = 0;
//		int right nums.size() - 1;//定义target在作弊又开区间，[left ,right]
//		while (left <= right)//当Left = right,区间[left right]依旧有效，所以用=
//		{
//			int middle = left + ((right - left) / 2);//防止溢出等同于（left+right)/2
//			if (nums[middle] > target)//target在左区间，[left,middle-1]
//			{
//				right = middle - 1;
//			}
//			else if (nums[middle] < target)//target在哦右区间，[middle+1,right]
//			{
//				left = middle + 1;
//			}
//			else//nusm[middle] == target
//			{
//				return middle;
//			}
//		}
//		//未找到目标
//		return -1;
//	}
//};
////第二种方法
//class Solution {
//public:
//	int search(vector<int>& nums, int target)
//	{
//		int left = 0;
//		int right = nums.size();//定义target在左闭右开区间，即：[left,right]
//		while (left < right)//因为left == right的时候，在[left,right)
//		{
//			int middle = left + ((right - left) >> 1);
//			if (num[middle] > target)//在左边区间，[left,middle）
//			{
//				right = middle;//target
//			}
//			else if (nums[middle] < target)
//			{
//				left = middle + 1;//target 在右区间，在[middle,right)
//			}
//			else//nums[middle]== taraget
//			{
//				return middle;//数组中找到目标值，直接返回下标
//			}
//		}
//		return -1;
//	}
//};
//
//
//class Solution {
//public:
//	int searchInsert(vector<int>& nums, int target) {
//		int n = nums.size();
//		int left = 0;
//		int right = n - 1;
//		while (left <= right)//当left= right时，区间依旧有效，[left,right]
//		{
//			int middle = left + (right - left) / 2;//计算中间下标位置，防止溢出
//			if (nums[middle] < target)//在右区间，[middle+1,right]
//			{
//				left = middle + 1;
//			}
//			else if (nums[middle] > target)//在左区间，[left,middle-1]
//			{
//				right = middle - 1;
//			}
//			else//nums[middle] == target
//			{
//				return middle;
//			}
//		}
//		return n + 1;
//	}
//};
//
//
